package demo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class RandomizedSet {

    List<Integer> list;
    Map<Integer, Integer> map;

    public RandomizedSet() {
        map = new HashMap<>();
        list=new ArrayList<>();
    }
    
    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }else{
            map.put(val, list.size());
            list.add(val);
            return true;
        }
    }
    
    public boolean remove(int val) {
        if(map.containsKey(val)){
            int index = map.get(val);
            // 将最后一个元素放到要删除的元素位置
            list.set(index, list.get(list.size()-1));
            map.put(list.get(index), index);
            list.remove(list.size()-1);
            map.remove(val);
            return true;
        }
        return false;
    }
    
    public int getRandom() {
        return list.get((int)(Math.random()*list.size()));
    }

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        randomizedSet.insert(1);
        randomizedSet.remove(2);
        randomizedSet.insert(2);
       System.out.println( randomizedSet.getRandom());
    }
}

